package org.shj.algorithm.dhsjjg.sort;

import org.shj.algorithm.dhsjjg.mintree.Kruskal;

import java.util.Stack;

/**
 * @author Shen Huang Jian
 * @date 2020-09-01 17:32
 */
public class SortUtils {

    public static int M = Integer.MAX_VALUE;

    public static void main(String[] args){
        /*int[] arr = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20};
        quickSort(arr);
        Sort.print(arr);*/

        //getMinPath(init(), 0, 8);

//        int[] numbers = new int[]{1, -2, 3, 10, -4, 7, -22, 5};
//        maxSubSum(numbers);

//        int[][] edgeArr = Kruskal.init();
//        minPath(edgeArr);

        String b = "acdfge";
        String a = "adfce";

//        getLcs(a, b);
        System.out.println(gongyinshu(32, 24));

    }

    public static int gongyinshu(int a,int b) {
        if(a<b) {
            int t=b;
            b=a;
            a=t;
        }

        while(b!=0) {
            if(a==b)
                return a;
            int x=b;
            b=a%b;
            a=x;
        }

        return a;
    }

    private static void getLcs(String a, String b){
        Info[][] infos = new Info[a.length() + 1][b.length() + 1];
        for(int i = 0; i <= a.length(); i++){
            Info info = new Info();
            info.setLcs(0);
            infos[i][0] = info;
        }

        for(int i = 0; i <= b.length(); i++){
            Info info = new Info();
            info.setLcs(0);
            infos[0][i] = info;
        }

        for(int i = 1; i <= a.length(); i++){
            for(int j = 1; j <= b.length(); j++){
                Info left = infos[i][j-1];
                Info up = infos[i-1][j];
                Info lu = infos[i-1][j-1];

                Info current = new Info();

                if(lu.getLcs() >= left.getLcs() && lu.getLcs() >= up.getLcs()){
                    current.setLcs(lu.getLcs());
                    current.setDirection("LU");

                }else if(left.getLcs() >= lu.getLcs() && left.getLcs() >= up.getLcs()){
                    current.setLcs(left.getLcs());
                    current.setDirection("LE");

                }else if(up.getLcs() >= lu.getLcs() && up.getLcs() >= left.getLcs()){
                    current.setLcs(left.getLcs());
                    current.setDirection("UP");
                }

                if(a.charAt(i - 1) == b.charAt(j - 1)){
                    current.setLcs(current.getLcs() + 1);
                }
                infos[i][j] = current;
            }

        }

        Stack<String> stack = new Stack<>();
        int i = a.length();
        int j = b.length();
        Info last = null;
        Info previous = null;

        while(true){
            if(i == 0 && j == 0){
                break;
            }
            last = infos[i][j];
            if("UP".equals(last.getDirection())){
                i -= 1;
            }else if("LU".equals(last.getDirection())){
                i -= 1;
                j -= 1;
            }else{
                j -= 1;
            }
            previous = infos[i][j];
            if(previous.getLcs() < last.getLcs()){
                stack.push(a.charAt(i) + "");
            }

        }

        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }

    }

    public static void minPath(int[][] edgeArr){
        int length = edgeArr.length;
        int[] arc = new int[length];

        int s, e;

        for(int i = 0; i < length; i++){
            s = findParent(arc, edgeArr[i][0]);
            e = findParent(arc, edgeArr[i][1]);
            if(s != e){
                arc[s] = e;
                System.out.println("V" + edgeArr[i][0] + "-->V" + edgeArr[i][1]);
            }
        }
    }

    private static int findParent(int[] arc, int p){
        while(arc[p] > 0){
            p = arc[p];
        }
        return p;
    }

    public static void maxSubSum(int[] arr){
        int sum = 0;
        int max = 0;
        for(int i = 0 ; i < arr.length; i++){

            if(sum > 0){
                sum += arr[i];
            }else{
                sum = arr[i] > 0 ? arr[i] : 0;
            }
            if(sum >= max){
                max = sum;
            }
        }
    }

    public static void getMinPath(int[][] paths, int begin, int end){
        int length = paths.length;
        int[][] pathMatrix = new int[length][length];
        for(int i = 0; i < length; i++){
            for(int j = 0; j < length; j++){
                pathMatrix[i][j] = j;
            }
        }

        int v,w,k;
        for(k = 0 ; k < length; ++k){  //k -- 所有的顶点都通过 k点中转
            for(v = 0; v < length; ++v){ //v -- 起始点
                for(w = 0 ; w < length; ++w){ //w -- 结束点
                    if(paths[v][k] != M && paths[k][w] != M && paths[v][w] > paths[v][k] + paths[k][w]){ //经过下标为k顶点的路径比原两点间路径更短
                        pathMatrix[v][w] = pathMatrix[v][k];    //路径设置经过下标为k的顶点
                        paths[v][w] = paths[v][k] + paths[k][w];
                    }
                }
            }
        }

        while( begin != end){
            System.out.print("V" + begin + "-->");
            begin = pathMatrix[begin][end];
        }
        System.out.print("V" + end);

    }





    public static void quickSort(int[] arr){
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int i, int j){
        int pos = partitionPos(arr, i, j);
        if(pos != -1){
            quickSort(arr, i, pos - 1);
            quickSort(arr, pos + 1, j);
        }

    }

    private static int partitionPos(int[] arr, int i, int j){
        if(i >= j){
            return -1;
        }
        if(i + 1 == j){
            if(arr[i] > arr[j]){
                Sort.swap(arr, i, j);
            }
            return -1;
        }
        int low = i;
        int high = j;

        int tmp = arr[low];

        while(low < high){
            while(low < high && arr[high] > tmp){
                high--;
            }
            while(low < high && arr[low] <= tmp){
                low++;
            }
            if(low < high){
                Sort.swap(arr, low, high);
            }

        }
        Sort.swap(arr, i, low);
        return low;
    }

    public static class Info{
        private int lcs;
        private String direction;

        public int getLcs() {
            return lcs;
        }

        public void setLcs(int lcs) {
            this.lcs = lcs;
        }

        public String getDirection() {
            return direction;
        }

        public void setDirection(String direction) {
            this.direction = direction;
        }
    }

    private static int[][] init(){
        return new int[][]{
                {0, 1, 5, M, M, M, M, M, M},
                {1, 0, 3, 7, 5, M, M, M, M},
                {5, 3, 0, M, 1, 7, M, M, M},
                {M, 7, M, 0, 2, M, 3, M, M},
                {M, 5, 1, 2, 0, 3, 6, 9, M},
                {M, M, 7, M, 3, 0, M, 5, M},
                {M, M, M, 3, 6, M, 0, 2, 7},
                {M, M ,M, M, 9, 5, 2, 0, 4},
                {M, M, M, M, M, M, 7, 4, 0}

        };
    }
}
